package com.lft.linked.list03.sorted_linked_list;

/**
 * 有序链表
 */
public class SortedLinkedListDemo {
	public static void main(String[] args) {
		SortedLinkedList list = new SortedLinkedList();
		list.insert(1);
		list.insert(3);
		list.insert(2);
		list.insert(5);
		list.insert(4);
		list.insert(6);
		// 遍历
		list.displayList();
		// 查询最小最大值
		System.out.println("获得最小值为：" + list.getMin());
		System.out.println("获得最大值为：" + list.getMax());
	}
}

class SortedLinkedList {
	
	private Node first;
	private Node last;
	
	public SortedLinkedList() {
		this.first = null;
	}
	
	/**
	 * 判断链表是否为空
	 * @return 链表空返回 true,否则返回false
	 */
	public boolean isEmpty() {
		return this.first == null;
	}
	
	/**
	 * 按顺序插入
	 * @param data 要插入的数值
	 */
	public void insert(int data) {
		Node newNode = new Node(data);
		Node pre = null;
		Node cur = this.first;
		if (isEmpty()) {
			this.last = newNode;
		}
		// 寻找插入的位置
		while (cur != null && data > cur.getData()) {
			pre = cur;
			cur = cur.getNext();
		}
		// 要插入的在 first 节点之前
		if (pre == null) {
			this.first = newNode;
			newNode.setNext(cur);
		}
		// 要插入的在 last 节点之后。
		else if (cur == null) {
			this.last.setNext(newNode);
			this.last = newNode;
		}
		// 任意位置
		else {
			pre.setNext(newNode);
			newNode.setNext(cur);
		}
	}
	
	/**
	 * 取得最小值。
	 * @return
	 */
	public int getMin() {
		return this.first.getData();
	}
	
	/**
	 * 取得最大值。
	 * @return
	 */
	public int getMax() {
		return this.last.getData();
	}
	
	/**
	 * 从头部删除一个节点
	 * @return
	 */
	public Node removeFirst() {
		Node temp = this.first;
		this.first = this.first.getNext();
		return temp;
	}
	
	/**
	 * 遍历链表
	 */
	public void displayList() {
		Node cur = this.first;
		while (cur != null) {
			cur.displayNode();
			cur = cur.getNext();
		}
		System.out.println();
	}
}

class Node {
	private int data;//数据域
	private Node next;//引用域
	
	public Node(int data) {
		this.data = data;
	}
	
	public int getData() {
		return data;
	}
	
	public void setData(int data) {
		this.data = data;
	}
	
	public Node getNext() {
		return next;
	}
	
	public void setNext(Node next) {
		this.next = next;
	}
	
	//打印链结点数据域内容
	public void displayNode() {
		System.out.print(data + "  ");
	}
}
